package array;

/**
 * 返回满足给定数值的最小子序列之和
 * @author liumingju
 * @date 2025/3/11 19:42
 */
public class 最小长度子序列之和 {
    public static void main(String[] args) {
        int[] nums = {2,3,1,2,4,3};
        int target = 7;
        System.out.println(getMinLength(nums, target));
        System.out.println(getMinLength02(nums,target));
    }

    // 暴力解法：一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成一个不断搜索区间的过程
    // 拓展：通过数据结构，保存本次遍历的左边界与右边界，即可返回子数组
    public static int getMinLength(int[] nums,int target){
        int minLength = Integer.MAX_VALUE;

        for(int i = 0;i<nums.length;i++){
            // 不需要从头开始，因为[A，B]与[B，A]是相同的
            int tempLength = 0;
            int tempTotal = 0;
            for(int j = i;j<nums.length;j++){
                tempLength++;
                tempTotal = tempTotal+nums[j];
                if(tempTotal>=target){
                    break;
                }
            }
            // 本次遍历找到了目标的子序列才需要更新，否则类似直接来到数组末尾，只有一个数字，比目标小，会直接返回1
            if(tempTotal>=target){
                minLength = Math.min(tempLength, minLength);
            }
        }
        return minLength;
    }

    // 滑动窗口
    // 通过窗口不断向后移动，记录符合条件的最短子数组长度
    // 滑动窗口的实现：一个for循环指向结束节点，并在该for循环更新起始节点
    // 起始节点的更新标准为：窗口实际值>=窗口阈值
    public static int getMinLength02(int[] nums,int target){
        int minLength = Integer.MAX_VALUE;
        int tempTotal= 0;
        int begin = 0;
        for(int end =0;end<nums.length;end++){
            tempTotal = tempTotal+nums[end];
            while (tempTotal>=target){
                // 计算本次窗口的长度
                int tempLength = end-begin+1;
                // 窗口的实际值大于窗口阈值，可以从左边缩小窗口
                tempTotal -= nums[begin++];
                minLength = Math.min(tempLength,minLength);

            }
        }
      return minLength;

    }


}
